n = int(input())
c = [int(x) for x in input().split()]
s = []
for i in range(n):
s.append(input())
v = 0
w = c[0]
inf = 10**16
new,newr = s[0],s[0][::-1]
for i in range(1,n):
last,lastr = new,newr
new,newr = s[i],s[i][::-1]
V = [inf]
if last <=new: V.append(v)
if lastr<=new: V.append(w)
W = [inf]
if last <=newr: W.append(v)
if lastr<=newr: W.append(w)
v,w = min(V), min(W)+c[i]
score = min(v,w)
print(score if score<inf else -1)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int N = 2e5 + 5;
const int M = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(0),
cin.tie(0);
int n;
cin >> n;
vector<string> v(n + 2);
int c[n + 2], dp[n + 2][2];
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
dp[1][0] = 0;
dp[1][1] = c[1];
for (int i = 2; i <= n; i++)
{
dp[i][0] = dp[i][1] = INF;
if (dp[i - 1][0] != INF)
{
if (v[i] >= v[i - 1])
dp[i][0] = dp[i - 1][0];
string rev = v[i];
reverse(rev.begin(), rev.end());
if (rev >= v[i - 1])
dp[i][1] = dp[i - 1][0] + c[i];
}
if (dp[i - 1][1] != INF)
{
string rev = v[i - 1];
reverse(rev.begin(), rev.end());
if (v[i] >= rev)
dp[i][0] = min(dp[i][0], dp[i - 1][1]);
string rev2 = v[i];
reverse(rev2.begin(), rev2.end());
if (rev2 >= rev)
dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i]);
}
}
int ans = min(dp[n][0], dp[n][1]);
if (ans == INF)
cout << "-1";
else
cout << ans;
}Health of a person | Divisibility |
A. Movement | Numbers in a matrix |
Sequences | Split houses |
Divisible | Three primes |
Coprimes | Cost of balloons |
One String No Trouble | Help Jarvis! |
Lift queries | Goki and his breakup |
Ali and Helping innocent people | Book of Potion making |
Duration | Birthday Party |
e-maze-in | Bricks Game |
Char Sum | Two Strings |
Anagrams | Prime Number |
Lexical Sorting Reloaded | 1514A - Perfectly Imperfect Array |
580A- Kefa and First Steps | 1472B- Fair Division |
996A - Hit the Lottery | MSNSADM1 Football |